import tool.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列 。
 *
 * 举个例子，如上图所示，给定一棵叶值序列为(6, 7, 4, 9, 8)的树。
 *
 * 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。
 *
 * 如果给定的两个根结点分别为root1 和root2的树是叶相似的，则返回true；否则返回 false 。
 *
 * 示例 1：
 * 输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
 * 输出：true
 *
 * 示例 2：
 * 输入：root1 = [1], root2 = [1]
 * 输出：true
 *
 * 示例 3：
 * 输入：root1 = [1], root2 = [2]
 * 输出：false
 *
 * 示例 4：
 * 输入：root1 = [1,2], root2 = [2,2]
 * 输出：true
 *
 * 示例 5：
 * 输入：root1 = [1,2,3], root2 = [1,3,2]
 * 输出：false
 *
 * 提示：
 * 给定的两棵树可能会有1到 200个结点。
 * 给定的两棵树上的值介于 0 到 200 之间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/leaf-similar-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q00872s {

    private List<Integer> list;

    private int idx;

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        list = new ArrayList<>();
        idx = 0;
        dfs1(root1);
        return dfs2(root2) && idx == list.size(); // root2是root1的子集，并且与root1的list大小相等，则表示完全相似
    }

    /**
     * 以中序遍历的方式，将root1的叶子节点值放入list中
     * @param root1
     */
    private void dfs1(TreeNode root1) {
        if (root1 == null) return;
        dfs1(root1.left);
        if (root1.left == null && root1.right == null) {
            list.add(root1.val);
        }
        dfs1(root1.right);
    }

    /**
     * 中序遍历时，挨个判断root2的叶子节点的值，与list对应下标的值是否相等
     * @param root2
     * @return
     */
    private boolean dfs2(TreeNode root2) {
        if (root2 == null) return true;
        if (!dfs2(root2.left)) return false;
        if (root2.left == null && root2.right == null) {
            if (idx == list.size() || list.get(idx++) != root2.val) return false;
        }
        return dfs2(root2.right);
    }

}
